#define _CRT_SECURE_NO_WARNINGS 1


#include<assert.h>
#include<iostream>

using namespace std;

template<class T>
struct AVLTreeNode
{
	AVLTreeNode<T>* _left;
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	int _bf;
	T data;

	AVLTreeNode(const T& data = T())
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _data(data)
	{ }
};

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	void RotateR(Node* parent)
	{
		Node* sub_left = parent->_left;
		Node* sub_left_right = sub_left->_right;
		Node* parent_parent = parent->_parent;
		parent->_left = sub_left_right;
		if (sub_left_right)
		{
			sub_left_right->_parent = parent;
		}
		sub_left->_right = parent;
		parent->_parent = sub_left;
		if (parent_parent == nullptr)
		{
			_root = sub_left;
		}
		else
		{
			if (parent == parent_parent->_left)
			{
				parent_parent->_left = sub_left;
			}
			else
			{
				parent_parent->_right = sub_left;
			}
		}
		sub_left->_parent = parent_parent;
		sub_left->_bf = parent->_bf = 0;
	}

	void RotateL(Node* parent)
	{
		Node* sub_right = parent->_right;
		Node* sub_right_left = sub_right->_left;
		Node* parent_parent = parent->_parent;
		parent->_right = sub_right_left;
		if (sub_right_left)
		{
			sub_right_left->_parent = parent;
		}
		sub_right->_left = parent;
		parent->_parent = sub_right;
		if (parent_parent == nullptr)
		{
			_root = sub_right;
		}
		else
		{
			if (parent == parent_parent->_left)
			{
				parent_parent->_left = sub_right;
			}
			else
			{
				parent_parent->_right = sub_right;
			}
		}
		sub_right->_parent = parent_parent;
		sub_right->_bf = parent->_bf = 0;
	}

	void RotateLR(Node* parent)
	{

	}

	bool insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (data > cur->data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (data < cur->data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (cur->data > parent->data)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

private:
	Node* _root = nullptr;
};